package com.atwy.sort;

import java.util.Arrays;

/**
 * 归并排序，是建立在归并操作上的一种有效的排序算法。
 * 大方向：二叉树的后序遍历理念，左右子树都处理完了，即左右都排好序之后，再进行合并
 *
 * 合并使用双指针
 *
 */
public class MergeSorting2 {
    public static void main(String[] args) {
        int[] array = {3, 65, 2, 34, 12, 5, 9, 12};
        new MergeSorting2().sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
    }
    // 辅助数组，这样避免多次申请内存
    int[] temp;
    public void sort(int[] array) {
        temp = new int[array.length];

        sort(array,0,array.length-1);
    }
    void sort(int[] array,int start,int end){
        if(start == end){
            return;
        }
        int mid = (end - start)/2 + start;
        sort(array,start,mid);
        sort(array,mid+1,end);

        merge(array,start,mid,end);
    }

    void merge(int[] array, int start, int mid, int end) {
        // 将array数组放到temp数组
        for (int i = start; i <= end; i++) {
            temp[i] = array[i];
        }
        // p1指向左边已排好序的数组起始位置，p2指向右边已排好序的数组起始位置
        int p1 = start,p2 = mid+1;
        for (int i = start; i <= end; i++) {
            if(p1 == mid+1){
                // 说明左边已经处理完成
                array[i] = temp[p2++];
            }else if(p2 == end + 1){
                // 说明右边已经处理完成
                array[i] = temp[p1++];
            }else if(temp[p1] > temp[p2]){
                // p1、p2哪个指针对应的值小放到结果中去，然后对应的指针前进一步
                array[i] = temp[p2++];
            }else {
                array[i] = temp[p1++];
            }
        }
    }
}
/**
归并排序的应用
 1.temp数组时辅助数组，避免频繁申请内存
 2.每次子sort之后原数组是部分有序的，所以 merge时是两个有序子数组进行合并，
 所以试着理解下面这句
 * 主要在 merge 函数，我们在使用 merge 函数合并两个有序数组的时候，其实是可以知道一个元素 nums[i] 后边有多少个元素比 nums[i] 小的。
 利用两个指针p1，p2分别指向左右已排好序的数组起点，比p1指向元素小的范围一定是 [mid+1,p2)
 所以个数 = p2 - mid -1，但这个个数只是这次merge的结果，不过后面每次merge原理是一样的

力扣315题：
 给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

 示例 1：
 输入：nums = [5,2,6,1]
 输出：[2,1,1,0]
 解释：
 5 的右侧有 2 个更小的元素 (2 和 1)
 2 的右侧仅有 1 个更小的元素 (1)
 6 的右侧有 1 个更小的元素 (1)
 1 的右侧有 0 个更小的元素

 解答：
 * */
/**
 * class Solution {
 *     private class Pair{
 *         // 元素的值
 *         int val;
 *         // 元素最初的下标索引
 *         int id;
 *
 *         public Pair(int val, int id) {
 *             this.val = val;
 *             this.id = id;
 *         }
 *
 *     }
 *     // 辅助数组
 *     Pair[] temp;
 *     // 记录每个元素后面比自己小的个数
 *     int[] count;
 *
 *     public List<Integer> countSmaller(int[] nums) {
 *         int length = nums.length;
 *         temp = new Pair[length];
 *         count = new int[length];
 *         // 构建入参数组
 *         Pair[] array = new Pair[length];
 *         for (int i = 0; i < length; i++) {
 *             array[i] = new Pair(nums[i],i);
 *         }
 *         // 执行归并排序
 *         sort(array,0,length-1);
 *
 *         List<Integer> result = new LinkedList<>();
 *         for(int c : count){
 *             result.add(c);
 *         }
 *         return result;
 *     }
 *
 *     void sort(Pair[] array,int start,int end){
 *         if(start == end){
 *             return;
 *         }
 *         // 取中间值进行左右切分
 *         int mid = (end - start)/2 + start;
 *         // 划分数组分别处理
 *         sort(array,start,mid);
 *         sort(array,mid+1,end);
 *
 *         merge(array,start,mid,end);
 *     }
 *
 *     void merge(Pair[] array,int start,int mid,int end){
 *         // 将入参先赋值给辅助数组
 *         for (int i = start; i <= end; i++) {
 *             temp[i] = array[i];
 *         }
 *         // p1，p2分别指向左右已排好序的数组起点
 *         int p1 = start,p2 = mid+1;
 *         for (int i = start; i <= end; i++) {
 *             if(p1 == mid+1){
 *                 // 说明左边都已经放入array中，则此时只需要将p2指针的数据放入array中
 *                 array[i] = temp[p2++];
 *             }else if(p2 == end + 1){
 *                 // 说明右边都已经放入array中，则此时只需要将p1指针的数据放入array中
 *                 array[i] = temp[p1++];
 *                 // 当p1放入array时，说明p1指向的元素值小于p2了，那此时可以统计比该元素小的个数了，
 *                 // 个数 = [mid+1,p2)
 *                 count[array[i].id] += p2 - mid -1;
 *             }else if(temp[p1].val > temp[p2].val){
 *                 array[i] = temp[p2++];
 *
 *             }else {
 *                 // 当p1放入array时，说明p1指向的元素值小于p2了，那此时可以统计比该元素小的个数了，
 *                 // 个数 = [mid+1,p2)
 *                 array[i] = temp[p1++];
 *                 count[array[i].id] += p2 - mid -1;
 *             }
 *         }
 *     }
 *
 *
 * }
 */

/**
 * 力扣327，区间和的个数，运用了 归并排序框架 + 前缀和 + 滑动窗口
 * 值得多琢磨琢磨
 * class Solution {
 *     int lower;
 *     int upper;
 *     int result;
 *     long[] temp;
 *     public int countRangeSum(int[] nums, int lower, int upper) {
 *         this.lower = lower;
 *         this.upper = upper;
 *
 *         int length = nums.length;
 *         // 前缀和，使用long避免溢出
 *         long[] preSum = new long[length+1];
 *         for (int i = 0; i < length; i++) {
 *             preSum[i+1] = preSum[i] + (long)nums[i];
 *         }
 *
 *         sort(preSum);
 *         return result;
 *     }
 *     void sort(long[] preSum){
 *         int n = preSum.length;
 *         temp = new long[n];
 *         sort(preSum,0,n-1);
 *     }
 *
 *     void sort(long[] preSum,int start,int end){
 *         if(start == end){
 *             return;
 *         }
 *         int mid = (end - start)/2 + start;
 *         sort(preSum,start,mid);
 *         sort(preSum,mid+1,end);
 *
 *         merge(preSum,start,mid,end);
 *     }
 *     void merge(long[] preSum,int start,int mid,int end){
 *         for (int i = start; i <=end ; i++) {
 *             temp[i] = preSum[i];
 *         }
 *         // 需要明确，当前数组分左右子数组，左边是[start,mid]，右边是[mid+1,end]
 *         // 左右子数组里的元素下标和始祖数组的元素下标可能不一致了，但右子数组中所有元素的原始下标一定 > 左子数组元素的原始下标
 *         // p11,p22指向右子数组，p11窗口左侧，p22窗口右侧
 *         int p11 = mid+1,p22 = mid+1;
 *         for (int i = start; i <= mid; i++) {
 *             // 利用滑动窗口
 *             while (p11<=end && preSum[p11]-preSum[i]<lower){
 *                 p11++;
 *             }
 *             while (p22<=end && preSum[p22]-preSum[i]<=upper){
 *                 p22++;
 *             }
 *             result += p22-p11;
 *         }
 *
 *         int p1=start,p2=mid+1;
 *         for (int i = start; i <= end; i++) {
 *             if(p1 == mid+1){
 *                 preSum[i] = temp[p2++];
 *             }else if (p2 == end +1){
 *                 preSum[i] = temp[p1++];
 *             }else if (temp[p1]>temp[p2]){
 *                 preSum[i] = temp[p2++];
 *             }else {
 *                 preSum[i] = temp[p1++];
 *             }
 *         }
 *     }
 * }
 *
 *
 */
